home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 11331 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.2 KB  |  107 lines
  1. Path: seas.smu.edu!not-for-mail
  2. From: dbowman@post.smu.edu (Damon Bowman)
  3. Newsgroups: comp.lang.c++
  4. Subject: Don't understand the Comb sort method
  5. Date: 13 Mar 1996 17:27:47 -0600
  6. Organization: Southern Methodist University
  7. Sender: usenet@seas.smu.edu
  8. Message-ID: <31475c41.460876069@sun.cis.smu.edu>
  9. Reply-To: dbowman@post.smu.edu
  10. NNTP-Posting-Host: sun.cis.smu.edu
  11. X-Nntp-Posting-Host: ax4-20.ppp.smu.edu
  12. X-Newsreader: Forte Agent .99d/32.182
  13.  
  14.  
  15. I am just teaching myself C++, and my book uses the Comb sort in the
  16. array section as an example of how to sort an array of integers.
  17.  
  18. The Comb sort uses an offset value, which the book says is initialized
  19. to either 1 or to (8 * numberOfElements / 11), whichever is larger.
  20.  
  21. Why is 8 * numberOfElements / 11 used?
  22.  
  23. The strange part (to me) is that the only way 1 would be larger than
  24. (8 * n / 11) is if there were only 1 element, in which case the array
  25. would obviously not need sorting.
  26.  
  27. Here's the source code from the example, which I have compiled and
  28. run.  It works as advertised.
  29.  
  30. //C++ program that sorts arrays using the Comb Sort method
  31.  
  32. #include <iostream.h>
  33.  
  34. const int MAX = 10;
  35. const int TRUE = 1;
  36. const int FALSE = 0;
  37.  
  38. int obtainNumData()
  39. {
  40.     int m;
  41.     do
  42.      {
  43.         cout << "Enter number of data points [2 to " << MAX << "] : ";
  44.         cin >> m;
  45.         cout << "\n";
  46.     }
  47.     while (m < 2 || m > MAX);
  48.     return m;
  49. }
  50.  
  51. void inputArray(int intArr[], int n)
  52. {
  53.     for (int i = 0; i < n; i++)
  54.         {
  55.         cout << "arr[" << i << "] : ";
  56.         cin >> intArr[i];
  57.         }
  58. }
  59.  
  60. void showArray(int intArr[], int n)
  61. {
  62.     for (int i = 0; i < n; i++)
  63.         {
  64.         cout.width(5);
  65.         cout << intArr[i] << " ";
  66.         }
  67.     cout << "\n";
  68. }
  69.  
  70. void sortArray(int intArr[], int n)
  71. {
  72.     int offset, temp, inOrder;
  73.     offset = n;
  74.     do
  75.     {
  76.         offset = (8 * offset) / 11;
  77.         offset = (offset == 0) ? 1 : offset;
  78.         inOrder = TRUE;
  79.         for (int i = 0, j = offset; i < (n-offset); i++, j++)
  80.         {
  81.             if (intArr[i] > intArr[j])
  82.             {
  83.                 inOrder = FALSE;
  84.                 temp = intArr[i];
  85.                 intArr[i] = intArr[j];
  86.                 intArr[j] = temp;
  87.             }
  88.         }
  89.     }
  90.     while (!(offset = 1 && inOrder == TRUE));    
  91. }
  92.  
  93. main()
  94. {
  95.     int arr[MAX];
  96.     int n;
  97.  
  98.     n = obtainNumData();
  99.     inputArray(arr, n);
  100.     cout << "Unordered array is:\n";
  101.     showArray(arr, n);
  102.     sortArray(arr, n);
  103.     cout << "\nSorted Array is:\n";
  104.     showArray(arr, n);
  105.     return 0;
  106. }
  107.